A common approach utilized in advanced industrial process control is Model-based Predictive Control, also known as “MPC”. MPC typically involves the use of a controller that utilizes a mathematical model of the process to predict its future behavior and to optimize it by adjusting manipulated variables. The accuracy of the internal process model is crucial to control performance.
Process control techniques are useful in a number of industrial and other applications. Such applications may be limited, for example, by processing power. For example, an embedded controller in an automobile engine exhibits less computing power than a personal computer (PC). Additionally, the sample time associated with power train issues typically runs in a very short time (e.g., milliseconds). Therefore, industrial processes might optimally be controlled in order to meet quality and production requirements. Modern complex industrial processes, however, require multiple control variables with interacting dynamics that exhibit time delays and lags, and nonlinearities. Various process control techniques can be adapted to handle such complex industrial processes. Current process control techniques utilize MPC to determine the optimum operation of a process by monitoring one or more characteristics of the process over time.
MPC is thus a standard control and optimization technique utilized in process control, such as, for example, power train control applications in diesel engines, turbocharger control, and so forth. The acronym “MPC” therefore generally refers to a class of algorithms, which utilize an internal mathematical model of the controlled system and an optimization algorithm to compute optimal future trajectories of, for example, automotive system inputs for control action. MPC is usually implemented in the context of the so-called “Receding Horizon” scheme. In typical receding horizon control schemes, the controller can calculate future trajectories of system inputs at each sampling period, but the first control action is generally applied to the system. The receding horizon scheme also introduces standard feedback for MPC controller.
A number of MPC approaches have been implemented and discussed in MPC-related literature. For example, the article entitled “Constrained model predictive control: Stability and optimality” by D. Q. Mayne, et al., Automatica 36 (2000), pp. 789-814, provides a good survey of MPC approaches and principals, and is incorporated herein by reference in its entirety. Another article, which is incorporated herein by reference, and which describes MPC principals and techniques is entitled “A survey of industrial model predictive control technology” by S. Joe Qin, et al., Control Engineering Practice 11 (2003), pp. 733-764.
Various control techniques and approaches, both MPC and/or non-MPC in nature, have also been implemented. For example, U.S. Pat. No. 7,155,334, entitled “Use of Sensors in a State Observer for a Diesel Engine”, which issued to Gregory E. Stewart et al on Dec. 26, 2006, and is assigned to Honeywell International Inc., discloses various techniques for controlling a diesel engine. U.S. Pat. No. 7,155,334 is incorporated herein by reference. U.S. Pat. No. 7,165,399, which issued to Gregory E. Stewart on Jan. 23, 2007, and is assigned to Honeywell International Inc., discusses the use of an MPC controller in association with a state observer in the context of an automotive system. U.S. Pat. No. 7,165,399 is also incorporated herein by reference.
Another prior art patent, which discloses the use of MPC techniques, is U.S. Pat. No. 7,275,374, entitled “Coordinated Multivariable Control of Fuel and Air in Engines,” which issued to Gregory E. Stewart et al on Oct. 2, 2007. U.S. Pat. No. 7,275,374, which is assigned to Honeywell International Inc., is also incorporated herein by reference. A further example of an MPC control system and methodology is disclosed in U.S. Pat. No. 7,328,577, entitled “Multivariable Control for an Engine,” which issued to Gregory E. Stewart et al on Feb. 12, 2008 and is assigned to Honeywell International Inc. U.S. Pat. No. 7,328,577 is incorporated herein by reference in its entirety.
MPC control can be formulated as a general optimization problem. The control objectives can be expressed by a criterion function or a cost function and by defining system constraints. The control action might be achieved by solving the optimization problem numerically at each sampling period. The time required to determine the optimal solution remains restrictive for relatively fast-sampling automotive systems even though efficient solvers have been proposed for certain class of optimization tasks, such as Linear Programming (LP) and Quadratic Programming (QP).
The overall performance of MPC can be significantly affected by the quality and accuracy of the utilized model, which is internally utilized by MPC to predict the future trajectories based on actual measurements. A nonlinear model may describe the behavior of a system relatively well, but it is more difficult to formulate and to solve MPC based on nonlinear MPC models than the linear models. A linear model can describe the dynamic behavior of the system well in a certain neighborhood of an operating point. The parameters of the linear model might be identified by utilizing data obtained from an identification experiment. A discrete-time linear model can be expressed, for example, in a state space form as indicated in equation (1.1) as follows:xk+1=Axk+Buk yk=Cxk+Duk  (1.1)wherein, xεÂnx represents the system state, uεÂnu is the system input, yεÂny is the system output and AεÂnx×nx, BεÂnx×nu, CεÂny×nx, DεÂny×nu are system matrices. This model can be utilized to predict future system trajectories based on information related to the current system state, i.e. xk. The prediction can be provided, for example, by equations (1.2) and (1.3) below.
                              [                                                                      x                                      k                    +                    1                                                                                                                        x                                      k                    +                    2                                                                                                      ⋮                                                                                      x                                      k                    +                    N                                                                                ]                =                                            [                                                                    A                                                                                                              A                      2                                                                                                            ⋮                                                                                                              A                      N                                                                                  ]                        ⁢                          x              k                                +                                    [                                                                    B                                                                                                                                                                                                                                                                                                                                                                                              AB                                                        B                                                                                                                                                                                                                                                                                            ⋮                                                        …                                                        ⋱                                                                                                                                                                                                                                        A                                                  N                          -                          1                                                                    ⁢                      B                                                                                                                          A                                                  N                          -                          2                                                                    ⁢                      B                                                                            …                                                        B                                                              ]                        ⁡                          [                                                                                          u                      k                                                                                                                                  u                                              k                        +                        1                                                                                                                                  ⋮                                                                                                              u                                              k                        +                        N                        -                        1                                                                                                        ]                                                          (        1.2        )                                          [                                                                      y                  k                                                                                                      y                                      k                    +                    1                                                                                                      ⋮                                                                                      y                                      k                    +                    N                    -                    1                                                                                ]                =                                            [                                                                    C                                                                                        CA                                                                                        ⋮                                                                                                              CA                                              N                        -                        1                                                                                                        ]                        ⁢                          x              k                                +                                    [                                                                    D                                                                                                                                                                                                                                                                                                                                                                                              CB                                                        D                                                                                                                                                                                                                                                                                            ⋮                                                        …                                                        ⋱                                                                                                                                                                                                                                        CA                                                  N                          -                          2                                                                    ⁢                      B                                                                            …                                                        CB                                                        D                                                              ]                        ⁡                          [                                                                                          u                      k                                                                                                                                  u                                              k                        +                        1                                                                                                                                  ⋮                                                                                                              u                                              k                        +                        N                        -                        1                                                                                                        ]                                                          (        1.3        )            
Using simplified notation, equations (1.2) and (1.3) can be written as{right arrow over (x)}=Pxxxk+Pux{right arrow over (u)}k {right arrow over (y)}=Pxyxk+Puy{right arrow over (u)}k  (1.4)wherein,
            x      →        =          [                                                  x                              k                +                1                                                                                        x                              k                +                2                                                                          ⋮                                                              x                              k                +                N                                                        ]        ,            y      →        =          [                                                  y              k                                                                          y                              k                +                1                                                                          ⋮                                                              y                              k                +                N                -                1                                                        ]        ,            u      →        =          [                                                  u              k                                                                          u                              k                +                1                                                                          ⋮                                                              u                              k                +                N                -                1                                                        ]      and Pxx, Pux, Pxy, Puy, are corresponding matrices.
In the optimization problem, the objectives for MPC control are generally expressed as a cost function. In linear MPC, the cost function may be quadratic with linear constraints, which leads to Quadratic Programming (QP) problems. Therefore, the final form of the cost function is influenced by many factors. The basic form can be written as indicated, for example, in equation (1.5) below:
                              J          ⁡                      (                                          u                →                            ,                              x                k                                      )                          =                                            x                              k                +                N                            T                        ⁢                          Q              N                        ⁢                          x                              k                +                N                                              +                                    ∑                              i                =                                  k                  +                  1                                                            k                +                N                -                1                                      ⁢                                          x                i                T                            ⁢                              Qx                i                                              +                                    ∑                              i                =                k                                            k                +                N                -                1                                      ⁢                                          u                i                T                            ⁢                              Ru                i                                                                        (        1.5        )            wherein, QεÂnx×nx, QNεÂnx×nx and RεÂnu×nu represent weighting matrices. If the control problem is to track a given reference signal, then the cost function can usually be written as
                              J          ⁡                      (                                          u                →                            ,                              x                k                                      )                          =                                            e                              k                +                N                            T                        ⁢                          Q              N                        ⁢                          e                              k                +                N                                              +                                    ∑                              i                =                                  k                  +                  1                                                            k                +                N                -                1                                      ⁢                                          e                i                T                            ⁢                              Qe                i                                              +                                    ∑                              i                =                k                                            k                +                N                -                1                                      ⁢                          Δ              ⁢                                                          ⁢                              u                i                T                            ⁢              R              ⁢                                                          ⁢              Δ              ⁢                                                          ⁢                              u                i                                                                        (        1.6        )            wherein, ek=yk−rk is the tracking error, rk is the reference signal and Δuk=uk−uk−1.
Using equation (1.4) and by introducing linear constraints, the optimization problem of MPC control can usually be transformed to the matrix form of equation (1.7) as follows:
                                          u            →                    *                =                              arg            ⁢                                                  ⁢                                          min                                  u                  →                                            ⁢                                                {                                                                                    1                        2                                            ⁢                                                                        u                          →                                                T                                            ⁢                      H                      ⁢                                                                                          ⁢                                              u                        →                                                              +                                                                  x                        k                        T                                            ⁢                      F                      ⁢                                                                                          ⁢                                              u                        →                                                              +                    β                                    }                                ⁢                                                                  ⁢                                  s                  .                  t                  .                                                                          ⁢                  G                                ⁢                                                                  ⁢                                  u                  →                                                              ≤                      W            +                          Vx              k                                                          (        1.7        )            wherein, H and F represent corresponding matrices and G, W and V represent matrices defining constraints. Then the control action at each sampling period can be obtained by solving the optimization problem of equation (1.7).
In the majority of prior art applications, the optimization problem might be formulated as Quadratic Programming (QP), if the model utilized by the MPC controller is linear. The QP problem as illustrated by equation (1.7) above can be solved numerically or explicitly in each sampling period for automotive systems with relatively large sampling periods. The numerical solution, however, is not possible for applications with relatively short sampling periods. The explicit solution to QP is well known as the Multi-Parametric Quadratic Programming (MP-QP) approach and enables relatively fast-sampling periods. The explicit solution to QP can be computed in two stages, which are typically divided into an off-line part and an on-line (i.e., “online”) part. The off-line part can be utilized for pre-computations in order to save on-line time in each sampling period of MPC control.
The standard MP-QP approach can transform the optimization problem of equation (1.7) by utilizing the following coordinate transformation illustrated by equation (1.8):z={right arrow over (u)}+H−1FTxk  (1.8)wherein, Z represents the new optimization vector of appropriate size. The new optimization problem is generally given by the following equation (1.9):
                                                        min              z                        ⁢                                          {                                                                            1                      2                                        ⁢                                          z                      T                                        ⁢                    H                    ⁢                                                                                  ⁢                    z                                    +                                      β                    _                                                  }                            ⁢                                                          ⁢                              s                .                t                .                                                                  ⁢                Gz                                              ≤                      W            +                          Sx              k                                      ,                  S          =                      V            +                                          GH                                  -                  1                                            ⁢                                                F                  T                                .                                                                        (        1.9        )            
The associated Lagrange function can be defined as
                              L          ⁡                      (                          z              ,              λ                        )                          =                                            1              2                        ⁢                          z              T                        ⁢            H            ⁢                                                  ⁢            z                    +                      β            _                    +                                                    (                                  Gz                  -                  W                  -                                      Sx                    k                                                  )                            T                        ⁢            λ                                              (        1.10        )            wherein, λεÂnC represents the vector of Lagrange multipliers. Then the optimality conditions (Karush-Kuhn-Tucker conditions) for a given problem can be expressed as follows:Hz+GTλ=0,Gz−W−Sxk≦0,λiAT(GiA−WiA−SiAxk)=0,λiA≧0.  (1.11)wherein, iA represents a set of indices of all active constraints. If I is the set of indices of all constraints and z*(xk) is the optimal solution to (1.9), then iA can be defined by the following equation (1.12):iA(xk)□{iεI;Giz*(xk)−Wi−Sixk=0}  (1.12)
Similarly, the set of inactive constraints can be defined by equation (1.13):iNA(xk)□{iεI;Giz*(xk)−Wi−Sixk<0}  (1.13)
Using the KKT conditions of equation (1.11) for optimal solution z*(xk) it holds, then:Hz*(xk)+GiATλiA*(xk)=0,GiAz*(xk)−WiA−SiAxk=0,GiNAz*(xk)−WiNA−SiNAxk<0,λiA*(xk)≧0,λiNA*(xk)=0.  (1.14)
Utilizing the first condition in equation (1.14) and assuming that matrix H0 is strictly positive definite, then,z*(xk)=−H−1GiATλiA*(xk)  (1.15)
Using equation (1.15) and second condition in (1.14) λiA* can be computed by equation (1.16) below:λiA*(xk)=−(GiAH−1GiAT)−1(WiA+SiAxk)  (1.16)and the optimal solution can be expressed as affine function of parameter vector xk z*(xk)=H−1GiAT(GiAH−1GiAT)−1(WiA+SiAxk)  (1.17)
Finally, the solution of equation (1.17) must satisfy constraints in equation (1.9) and Lagrange multipliers of equation (1.16) must be nonnegative, as is required by the fourth condition in equation (1.14). Both conditions can be rewritten to the form of (1.18) as follows:
                                          [                                                                                                                              GH                                                  -                          1                                                                    ⁢                                                                                                    G                                                          i                              Aj                                                        T                                                    ⁡                                                      (                                                                                          G                                                                  i                                  A                                                                                            ⁢                                                              H                                                                  -                                  1                                                                                            ⁢                                                              G                                                                  i                                  A                                                                T                                                                                      )                                                                                                    -                          1                                                                    ⁢                                              S                                                  i                          A                                                                                      -                    S                                                                                                                                                                  (                                                                              G                                                          i                              A                                                                                ⁢                                                      H                                                          -                              1                                                                                ⁢                                                      G                                                          i                              A                                                        T                                                                          )                                                                    -                        1                                                              ⁢                                          S                                              i                        A                                                                                                                  ]                    ⁢                                          ⁢                      x            k                          ≤                                  ⁢                                  ⁢                                  ⁢                  [                                          ⁢                                                                                                                -                                              GH                                                  -                          1                                                                                      ⁢                                                                                            G                                                      i                            Aj                                                    T                                                ⁡                                                  (                                                                                    G                                                              i                                A                                                                                      ⁢                                                          H                                                              -                                1                                                                                      ⁢                                                          G                                                              i                                A                                                            T                                                                                )                                                                                            -                        1                                                              ⁢                                          W                                              i                        A                                                                              +                  W                                                                                                                          -                                                                  (                                                                              G                                                          i                              A                                                                                ⁢                                                      H                                                          -                              1                                                                                ⁢                                                      G                                                          i                              A                                                        T                                                                          )                                                                    -                        1                                                                              ⁢                                      W                                          i                      A                                                                                                    ]                                    (        1.18        )            
FIGS. 1-2 illustrate example prior art graphs 100 and 200 which represent the constraints for optimization vector {right arrow over (u)}(xk) and critical regions for a parameter vector xk using a multi-parametric quadratic programming algorithm. The stored matrices from equation (1.8) to (1.18) can be utilized in the on-line part of the multi-parametric quadratic programming algorithm to determine the optimal solution {right arrow over (u)}*(xk) for the given parameter vector xk. As depicted in FIG. 1, system constraints for the optimization vector {right arrow over (u)}(xk) can be plotted using the stored matrices from equations (1.8) to (1.18). As illustrated in FIG. 2, the critical regions CRiA associated with a given set of active constraints indexed by iA can be defined by the inequality (1.18). The optimal solution associated with CRiA is given by (1.17). The optimal MPC control action {right arrow over (u)}*(xk) can be obtained by utilizing the transformation of equation (1.8) as follows:{right arrow over (u)}*(xk)=−H−1FTxk+z*(xk)  (1.19)
Therefore, the solution of the optimization problem (1.9) can be divided into the off-line part and on-line part.
FIG. 3 illustrates a high-level prior art flowchart depicting an off-line method 300 for the design and implementation of optimal multivariable MPC controllers utilizing an MP-QP algorithm. As indicated at block 310, the parameter space can be partitioned so that all partitions for all feasible combinations of constraints iA (1.18) and associated affine functions for z*(xk) (or more precisely uk*(xk) by using transformation (1.8)) can be computed for an optimal on-line control action. As depicted at block 320, the pre-computed critical regions CRiAj for j=1, 2, . . . n, wherein n is the total number of critical regions, and the affine functions for uk*(xk) are stored, the stored matrices are defined as follows:
                                          M            1            j                    =                      [                                                                                                                              GH                                                  -                          1                                                                    ⁢                                                                                                    G                                                          i                              Aj                                                        T                                                    ⁡                                                      (                                                                                          G                                                                  i                                  Aj                                                                                            ⁢                                                              H                                                                  -                                  1                                                                                            ⁢                                                              G                                                                  i                                  Aj                                                                T                                                                                      )                                                                                                    -                          1                                                                    ⁢                                              S                                                  i                          Aj                                                                                      -                    S                                                                                                                                                                  (                                                                              G                                                          i                              Aj                                                                                ⁢                                                      H                                                          -                              1                                                                                ⁢                                                      G                                                          i                              Aj                                                        T                                                                          )                                                                    -                        1                                                              ⁢                                          S                                              i                        Aj                                                                                                                  ]                          ⁢                                  ⁢                              m            1            j                    =                      [                                                                                                                              -                                                  GH                                                      -                            1                                                                                              ⁢                                                                                                    G                                                          i                              Aj                                                        T                                                    ⁡                                                      (                                                                                          G                                                                  i                                  Aj                                                                                            ⁢                                                              H                                                                  -                                  1                                                                                            ⁢                                                              G                                                                  i                                  Aj                                                                T                                                                                      )                                                                                                    -                          1                                                                    ⁢                                              W                                                  i                          Aj                                                                                      +                    W                                                                                                                                          -                                                                        (                                                                                    G                                                              i                                Aj                                                                                      ⁢                                                          H                                                              -                                1                                                                                      ⁢                                                          G                                                              i                                Aj                                                            T                                                                                )                                                                          -                          1                                                                                      ⁢                                          W                                              i                        Aj                                                                                                                  ]                          ⁢                                  ⁢                              M            2            j                    =                                    (                                                                    -                                          H                                              -                        1                                                                              ⁢                  F                                +                                                      H                                          -                      1                                                        ⁢                                                                                    G                                                  i                          Aj                                                T                                            ⁡                                              (                                                                              G                                                          i                              Aj                                                                                ⁢                                                      H                                                          -                              1                                                                                ⁢                                                      G                                                          i                              Aj                                                        T                                                                          )                                                                                    -                      1                                                        ⁢                                      S                                          i                      Aj                                                                                  )                                      (                                                1.                  ..                                ⁢                                  n                  u                                            )                                      ⁢                                  ⁢                              m            2            j                    =                                    (                                                H                                      -                    1                                                  ⁢                                                                            G                                              i                        Aj                                            T                                        ⁡                                          (                                                                        G                                                      i                            Aj                                                                          ⁢                                                  H                                                      -                            1                                                                          ⁢                                                  G                                                      i                            Aj                                                    T                                                                    )                                                                            -                    1                                                  ⁢                                  W                                      i                    Aj                                                              )                                      (                                                1.                  ..                                ⁢                                  n                  u                                            )                                                          (        1.20        )            
FIG. 4 illustrates a high-level prior art flowchart depicting an on-line method 400 for the design and implementation of optimal multivariable MPC controllers utilizing an MP-QP algorithm. As illustrated at block 410, actual value of parameter vector xk can be read in the on-line part. Next, as depicted at block 420, the active critical region CRiA can be determined for the actual value of parameter vector xk, and the optimal control law uk*(xk) can be computed by utilizing the associated affine function and the active critical region.
Such a standard MP-QP control approach solves the optimization problems for automotive applications, but requires a larger memory space for storing all pre-computed results. This memory consumption can restrict the usability of the MP-QP approach for relatively small control problems such as low-order systems, a small number of constraints and short constraints horizons. Unfortunately, the number of critical regions may be, in general, an exponential function of the number of constraints. Therefore, the MP-QP approach is not suitable for applications with limited memory capacity. It may be difficult, for such an approach, to implement MPC on embedded computing environments in automotive industry exhibiting fast sample times, and low memory and processor speed available for solving mathematical algorithms.
A need therefore exists for a method and system for design and implementation of optimal multivariable MPC controllers, which are well-suitable especially for fast-sampling dynamic systems in automotive applications with low memory. Such an improved method and system is described in greater detail herein.